package leetcode.array;

/**
 * @Description: https://leetcode.cn/problems/median-of-two-sorted-arrays/
 * @Author Ammar
 * @Create 2023/7/30 17:58
 */
public class _4_寻找两个正序数组的中位数 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        int left = 0, right = m;
        int totalLeft = (m + n + 1) / 2;
        while (left < right) {
            // 第一个数组中，分割线左边的元素个数
            int i = left + (right - left + 1) / 2;
            // 第二个数组中分割线左边元素的个数
            int j = totalLeft - i;

            if (nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                // 如果区间只有2个元素，会死循环
                left = i;
            }
        }
        int i = left;
        int j = totalLeft - i;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
        if (((m + n) % 2) == 1) {
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            return (double) ((Math.max(nums1LeftMax, nums2LeftMax)
                    + Math.min(nums1RightMin, nums2RightMin))) / 2;
        }
    }
}
